<html>
<head>
<TITLE>CSE5317/4305 Project #3</TITLE>
</head>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000">
<center>
<H1>CSE5317/4305 Project #3 (Abstract Syntax)</H1>
Due Wednesday March 12 at 11:59pm<p>
Worth 14% of your project grade
</center>
<p>
<hr>
<p>
For this project, you are asked to generate ASTs (Abstract Syntax Trees) for PCAT.
First you need to learn how to use the <a href="notes/node26.html">generic
abstract syntax trees (Gen)</a> used in the calculator example:
Study the Gen manual very carefully
and then see how it is used in <a href="calc/calc.gen">calc.gen</a>.
<p>
You need to put actions to your <tt>pcat.gen</tt> file to generate ASTs.
<p>
Your AST when printed should follow the following syntax,
where <tt>{ expression }</tt> means zero, one, or more expressions separated by commas (eg,
<tt>expression1 ',' expression2 ',' expression3</tt>)
and <tt>{',' expression }</tt> is equal to <tt>',' { expression }</tt> for one or more expressions
and equal to empty for zero expressions:
<pre>
program         -> ProcDecs '(' ProcDec '(' main ',' NoTyp '()' ',' body ')' ')'
body            -> BodyDef '('  { declarations } ',' statement ')'
declarations    -> VarDecs '(' { var-dec } ')'
                -> TypeDecs '(' { type-dec } ')'
                -> ProcDecs '(' { proc-dec } ')'
var-dec         -> VarDec '(' ID ',' type ',' expression ')'
type-dec        -> TypeDec '(' ID ',' type ')' 
proc-dec        -> ProcDec '(' ID ',' type  {',' formal-param } ',' body ')' 
type            -> NamedTyp '(' ID ')'
                -> ArrayTyp '(' type ')'
                -> RecordTyp '(' { component } ')'
                -> NoTyp '()'
                -> AnyTyp '()'
component       -> Comp '(' ID ',' type ')'
formal-param    -> Param '(' ID ',' type ')'
statement       -> AssignSt '(' lvalue ',' expression ')'
                -> CallSt '(' ID {',' expression } ')'
                -> ReadSt '(' { lvalue } ')'
                -> WriteSt '(' { expression } ')'
                -> IfSt '(' expression ',' statement ',' statement ')'
                -> WhileSt '(' expression ',' statement ')'
                -> LoopSt '(' statement ')'
                -> ForSt '(' ID ',' expression ',' expression ',' expression ',' statement ')'
                -> ExitSt '(' ')'
                -> RetSt '(' [ expression ] ')'
                -> SeqSt '(' { statement } ')'
expression      -> BinOpExp '(' binop ',' expression ',' expression ')'
                -> UnOpExp '(' unop ',' expression ')'
                -> LvalExp '(' lvalue ')'
                -> CallExp '(' ID {',' expression } ')'
                -> RecordExp '(' ID {',' record-init } ')'
                -> ArrayExp '(' ID {',' array-init } ')'
                -> IntConst '(' INTEGER_LITERAL ')'
                -> RealConst '(' REAL_LITERAL ')'
                -> StringConst '(' STRING_LITERAL ')'
record-init     -> RecordInit '(' ID ',' expression ')'
array-init      -> ArrayInit '(' expression ',' expression ')'      
lvalue          -> Var '(' ID ')'
                -> ArrayDeref '(' lvalue ',' expression ')'
                -> RecordDeref '(' lvalue ',' ID ')'
binop           -> gt | lt | eq | geq | leq | neq | plus | minus | times | slash | div | mod | and | or 
unop            -> minus | not
</pre>
where the <tt>binop</tt> and <tt>unop</tt> names are names of operators.
<p>
See the "Complete Concrete Syntax" section in the <a href="pcat04.pdf">PCAT manual</a>
to understand the relationship between the PCAT grammar and this output syntax.
For example, the AST of the PCAT expression <tt>(x-2)+3</tt> is constructed using Gen as follows::
<pre>
#&lt;BinOpExp(plus,BinOpExp(minus,LvalExp(Var(x)),IntConst(2)),IntConst(3))&gt;
</pre>
<p>
Hints: If a type is optional, return NoTyp() if missing. NIL has type AnyTyp().
To convert a list of statements
into a single statement use SeqSt. To convert a VAR declaration to a VarDec with one ID only, use
a loop to generate one VarDec for each VAR ID. Need to improvise for defaults: eg, if
the first expression of record-init is missing, use IntConst(1).
The first rule in the grammar should set the variable <tt>PcatParser.program_ast</tt>
to the entire AST of the source program because the next parser phases will use this value.
<p>
<b>New hint:</b> You need to pass the final Ast to the rest of the program. For example, the first rule may look like:
<pre>
program ::= PROGRAM IS body:b SEMI    {: PcatParser.program_ast = #&lt;ProcDecs(ProcDec(main,NoTyp(),`b))&gt;; :}
</pre>
<p>
You need to run your parser against all <tt>tests/*.pcat</tt> files.
For example:
<pre>
run 3 hello
</pre>
You also need to compare your output with that of the solution:
<pre>
solution 3 hello
</pre>
<p>
After ensuring that your program compiles and executes correctly,
cleanup your <tt>pcat</tt> directory using
<tt>
clean
</tt>
Then, if you are using Linux, archive your file using <tt>tar cvf pcat.tar pcat</tt>.
If you are using Windows, zip the whole directory into the file <tt>pcat.zip</tt>.
Then submit your file (<tt>pcat.tar</tt> or <tt>pcat.zip</tt>) here:
<p>
<form enctype="multipart/form-data" action="/cgi-bin/php/handin.php" method="POST">
    <input type="hidden" name="MAX_FILE_SIZE" value="10000000" />
    <input type="hidden" name="class" value="cse5317" />
    <input type="hidden" name="assignment" value="proj3" />
Submit this file: <input name="userfile" type="file" size="50"/><br/>
    <input type="submit" value="Send File" />
</form>
<p>
<hr>
<P>
<ADDRESS>Last modified: 03/06/08 by <A HREF="http://lambda.uta.edu/">Leonidas Fegaras</A></ADDRESS>
